#include <stdio.h>
#include <stdlib.h>

/*节点*/
typedef struct ListNode
{
	int data;//存放有效数据
    struct ListNode *next;//指向后继节点
}LIST_NODE;
/*链表*/
typedef struct List
{
	LIST_NODE *head;	//存放链表中第一个节点的地址
	int size ;//记录链表中节点的个数
}LIST;

LIST *list_create()
{
	LIST *list = malloc(sizeof(LIST));
	/*初始化成员变量*/
    list->head = NULL;
	list->size = 0;
	return list;
}
/*创建节点*/
LIST_NODE *node_create(int data)
{
	LIST_NODE *node = malloc(sizeof(LIST_NODE));
	node->data = data;
	node->next = NULL;
	return node;
}
/*前部插入*/
void list_insert(LIST *list, int data)
{
	LIST_NODE *node = node_create(data);
	node->next = list->head; 
   	list->head = node;
	list->size++;
}
/*后部插入*/
void list_insert2(LIST *list, int data)
{
	/*1 找到最后一个节点*/
    LIST_NODE *node = list->head;
	while(node != NULL)
	{
		if(node->next == NULL)//node指向最后一个节点
		{
			break;
		}
		node = node->next; //指向下个节点，继续判断是否为最后一个节点
	}
	/* 创建新的节点*/
	if(node != NULL)//原链表不为空
	{
		node->next = node_create(data);
	}
	else
	{
		list->head = node_create(data);
	}
	
}
void list_print(LIST *list)
{
	LIST_NODE *node = NULL;
	for(node=list->head; node; node=node->next)
	{
		printf("%d ", node->data);
	}
	printf("\n");
}
void list_del(LIST *list, int data)
{
	/*找到要删除的节点和它的前一个节点*/
	LIST_NODE *node = list->head;//指向第一个节点，可能为空链表
	LIST_NODE *prev = NULL;//保存要删除节点的前一个节点
	while(node != NULL)
	{
		if(node->data == data)//找到要删除的节点
		{	
			//如果要删除的节点为链表中第一个节点
			if(node == list->head)
			{
				list->head = node->next;
				free(node);
				node = list->head; // 指向下个节点继续循环判断
			}
			else //要删除的节点不为链表中的第一个节点
			{
				//从链表中剔除node指向的节点
				prev->next = node->next;
				free(node);
				node = prev->next; //指向刚删除节点的下一个节点
			}
		}
		else //该节点不是要删除的节点
		{
			prev = node;
			node = node->next; //指向下个节点继续循环判断
		}
	}
}
LIST_NODE *node_destroy(LIST_NODE *node)
{
	LIST_NODE *next = node->next;
	free(node);
	return next;
}
void list_destroy(LIST *list)
{
	/*清空链表，使其为空链表*/
	while(list->head)
	{
		list->head = node_destroy(list->head);
	}
	free(list);
}
void list_update(LIST *list, int old, int new)
{
	LIST_NODE *node = NULL;
	/*遍历链表中的每一个节点*/
	for(node=list->head; node; node=node->next)
	{
		if(node->data == old)
		{
			node->data = new;
		}
	}
}
int main()
{
	/*1 创建空单向链表*/
	LIST *list = list_create();
	/*2 插入节点*/
	list_insert(list, 11);
	list_insert(list, 22);
	list_insert(list, 22);
	list_insert(list, 22);
	list_insert(list, 22);
	list_insert(list, 22);
	list_insert(list, 33);
	list_insert(list, 44);
	list_insert(list, 55);
	list_insert(list, 66);
	list_insert2(list, 101);
	list_insert2(list, 102);
	list_insert2(list, 103);
	/*3 遍历链表*/
    list_print(list);
	/*4 删除链表中的节点*/
	list_del(list, 33);
	list_del(list, 11);
	list_del(list, 66);
    list_print(list);
	/*5 修改节点*/
    list_update(list, 22, 99);
    list_print(list);
	/*6 销毁链表*/
    list_destroy(list);

	return 0;
}






